
public class DivideTwoInteger {
	public int divide(int dividend, int divisor) {
		long a = 0, b = (long)Integer.MAX_VALUE+1;
		long d1 = dividend, d2 = divisor;
		
		boolean neg = false;
		if(d1 < (long)0) {
			d1 = -d1;
			neg = !neg;
		}
		if(d2 < (long)0) {
			d2 = -d2;
			neg = !neg;
		}
		
		System.out.println(d1+" "+d2+" "+neg);
		
//		if(divisor == 1) return dividend;
//		if(divisor == -1) return -dividend;
		
		while(a <= b) {
			
			long mid = (((long)b-(long)a)/2+(long)a);
			
			long curr = multi(mid, d2);
			
			System.out.println(a+" "+b+" "+mid+ " "+curr);
			
			if((long)d1 - curr >= 0 && (long)d1 - curr < d2) {
				return longToInt(mid, neg);
			}
			else if(curr > (long)d1) {
				b = mid - 1;
			}
			else if(curr < (long)d1) {
				a = mid + 1;
			}
		}
		
		return Integer.MAX_VALUE;
	}
	
	public int longToInt(long a, boolean neg) {
//		System.out.println(a+" "+neg);
		if(a == 2147483648l) {
			if(neg)
				return Integer.MIN_VALUE;
			else
				return Integer.MAX_VALUE;
		}
		else if(!neg)
			return (int)a;
		else
			return -(int)a;
	}
	
	public long multi(long a, long b) {
        long result = 0;
        if(Math.abs(b) > Math.abs(a)) {
//        if(b> a) {
        	long c = b;
            b = a;
            a = c;
        }
        
        if(b >= 0) {
        	for(int i = 0 ; i < b ; i++) {
                result = result + a;
//                System.out.println(result);
                if(result > (long)Integer.MAX_VALUE+2) return (long)Integer.MAX_VALUE + 2;
            }

            return result;
        }
        else {
        	for(int i = 0 ; i > b ; i--) {
                result = result - a;
            }

            return result;
        }
    }
	
//	public int divide3(int d1, int d2) {
//		if(d2 == 0) return Integer.MAX_VALUE;
//		String d1s = ""+d1, d2s = ""+d2;
//		boolean neg = false;
//		
//		if(d1 < 0) {
//			neg = !neg;
//			d1s = d1s.substring(1);
//		}
//		if(d2 < 0) {
//			neg = !neg;
//			d2s = d2s.substring(1);
//		}
//		
//		String out = "";
//		int len = d1s.length()-d2s.length();
//		int l = d2s.length();
//		
//		for(int i = 0 ; i < len; i++) {
//			int curr = 0;
//			while(Integer.parseInt(d1s.substring(0, l+1)) > 
//				Integer.parseInt(d2s.substring(0, l+1))) {
////				d1s = ()+d1s.substring(l+2)
//			}
//		}
//
//		return 0;
//	}
//	
//	public int divide2(int dividend, int divisor) {
//        if(divisor == 0) return Integer.MAX_VALUE;
//        if(divisor == 1) return dividend;
//        if(dividend != Integer.MIN_VALUE && Math.abs(dividend) < Math.abs(divisor)) return 0;
//        if(dividend == divisor) return 1;
//        
////        System.out.println("X "+dividend+" "+ divisor);
//        
//        
//        
//        boolean neg = false;
//        if(dividend < 0) {
//            neg = !neg;
//            dividend = -dividend;
//            if(dividend == Integer.MIN_VALUE) dividend = Integer.MAX_VALUE;
////            System.out.println(dividend);
//        }
//        if(divisor < 0) {
//            neg = !neg;
//            divisor = - divisor;
//            if(divisor == Integer.MIN_VALUE) divisor = Integer.MAX_VALUE;
////            System.out.println(divisor);
//        }
//        
////        if(divisor == 1 && !neg) return dividend;
////        if(divisor == 1 && neg) return -dividend;
//        
//        int i = 9;
//        while(i >= 0) {
//        	int t = multi10(divisor, i);
//            if(dividend >= t && t != -1) break;
//            else i--;
//        }
//        
//        // System.out.println(Integer.MAX_VALUE+" "+multi10(divisor, i));
//        
//        String result = "";
//        
//        for(int j = i ; j >= 0 ; j --) {
//            for(int k = 9 ; k >= 0 ; k--) {
//            	int t = multi(multi10(divisor, j), k);
//                if(dividend >= t && t != -1) {
//                    result = result + k;
//                    dividend = dividend - multi(multi10(divisor, j), k);
//                    break;
//                }
//            }
//        }
//        
//        if(result.length() == 0) return 0;
//        
//        if(!neg)
//        	return Integer.parseInt(result);
//        else
//        	return -Integer.parseInt(result);
//    }
//    
//    
//    
//    public int multi10(int a, int b) {
//        String astr = ""+a;
//        for(int i = 0 ; i < b ; i ++) {
//            astr = astr + "0";
//        }
//        
//        if(Long.parseLong(astr) > Integer.MAX_VALUE) return -1;
//        else return Integer.parseInt(astr);
//        
//    }
}

